 1.车货匹配之需求介绍
   
   在物流系统中，为了保证提供给客户及时高效的送货服务，我们需要在就近仓库提前储备相关商品。在
面对二级仓库的补货需求时一级仓库需要基于货物数量合理安排车辆送货。
   运输车辆规格信息：
   货车（厢式/板车）车型：xxx 实际载重量：25吨/60立方米
   备注：实际装车过程中，由于大部分商品都是日常百货用品，所以往往会先达到容积的限制但是载重可
能还有很大余量。所以在解决实际问题时我们只需考虑如何尽可能满足空间。
   一级仓库与二级仓库之间的货物调配每天都会进行，二级仓库每天会向一级仓库发送很多补货订单，
   一个二级仓库的补货订单信息示例如下：
ID    pack_total_volume
10001 1.18041
10002 8.92088
10003 4.58139
10004 5.29266
10005 1.23892
10006 3.93005
10007 7.53638
10008 6.92084
10009 3.89288
10010 4.67208
10011 0.37816
10012 0.7633
10013 1.49049
10014 0.2945
10015 3.63577
10016 4.53125
10017 6.86774
10018 7.03136
10019 8.32038
10020 3.28645
10021 0.92165
10022 6.0227
10023 6.67724
10024 2.25087
10025 6.36347  
   
   备注：一级仓库在每天五点之后会收集汇总每个二级仓库的补货信息，然后相同品类商品打包汇总之后
生成如上运单信息，然后调配车辆进行运输。
   对于这个场景中我们需要合理组合货物，保证尽量充分利用每辆车的空间来减少发车数量，降低企业的
成本支出！！
   总结：基于上面的分析，发现该问题是一个求最优解的问题。所以选择使用动态规划算法实现！！

 2.思路分析
   
   1).定义状态
   volumeArr=
[1.18041,8.92088,4.58139,5.29266,1.23892,3.93005,7.53638,6.92084,3.89288,4.67208,0.37816,0.7633..]
   求解的是最少空间
   dp[i][j]
   含义：前i件物品在不超过最大容积j的时的最大体积
   2).确定状态转移方程
   参照01背包问题
   dp(i,j)=dp(i-1,j-1)，确定这两者之间的关系
   如果只剩最后一件物品时，有两种情况
       不选择该物品：dp(i,j)=dp(i-1,j)
       选择该物品：dp(i,j)=dp(i-1,j-volumeArr[i-1])+volumeArr[i-1]
   dp(i,j)返回的是最大体积
   max(dp(i-1,j),dp(i-1,j-volumeArr[i-1])+volumeArr[i-1])
   
 3.代码开发
   
   1).代码实现
   参考01背包问题代码实现
package com.lg.transport_goods;

//参考01背包实现
public class TransportGoods {
    public static int getMaxVolune(int[] volumeArr, int capcity) {
        //定义状态数组
        int[][] dp=new int[volumeArr.length+1][capcity+1];
        //遍历数据
        for (int i = 1; i <=volumeArr.length; i++) {
            for (int j = 1; j <=capcity; j++) {
                //状态方程
                if (j < volumeArr[i-1]) {
                    //剩余容积不满足选择该物品
                    dp[i][j]=dp[i-1][j];
                } else {
                    //选或不选
                    dp[i][j]=Math.max(dp[i-1][j-volumeArr[i-1]]+volumeArr[i-1], dp[i-1][j]);
                }
            }
        }
        return dp[volumeArr.length][capcity];
    }

    public static void main(String[] args) {
        int[] volumeArr={1, 2, 3, 4, 5, 6};
        int capcity=10;
        System.out.println(getMaxVolune(volumeArr, capcity));
    }
}
   
   细节补充：
   (1)、打印物品组合方案
   实现01背包问题中物品组合方案的打印
package com.lg.packsack;

/**
 * 使用动态规划解决01背包问题
 */
public class PackSack {
    public static void main(String[] args) {
        int[] values= {6,3,5,4,6};
        int[] weights={11,2,2,6,5,4};
        int capacity=10;
        System.out.println(getMaxVal(values, weights, capacity));
    }

    static int getMaxVal(int[] values, int[] weights, int capacity) {
        //过滤掉不合理的值
        if(values==null || values.length==0){return 0;}
        if (weights==null || weights.length==0){return 0;}
        if (capacity<0){return 0;}
        //使用递推方式:dp(i,j):最大承重为j，有前i件物品可选时的最大总价值
        int[][] dp=new int[values.length+1][capacity+1];//数组初始化默认值就是0
        //遍历
        for (int i = 1; i <= values.length; i++) {
            for (int j = 1; j <= capacity; j++) {
                //翻译状态转移方程
                if (j < weights[i-1]) {
                    dp[i][j]=dp[i-1][j];
                } else {
                    dp[i][j]=Math.max(dp[i-1][j], dp[i-1][j-weights[i-1]]+values[i-1]);
                }
            }
        }
        return dp[values.length][capacity];
    }   
}   
   递推填表   
   打印货运组合方案信息
   注意：数组索引越界异常
 package com.lg.packsack;

/**
 * 使用动态规划解决01背包问题
 */
public class PackSack {
    public static void main(String[] args) {
        int[] values= {6,3,5,4,6};
        int[] weights={11,2,2,6,5,4};
        int capacity=10;
        System.out.println(getMaxVal(values, weights, capacity));
    }

    static int getMaxVal(int[] values, int[] weights, int capacity) {
        //过滤掉不合理的值
        if(values==null || values.length==0){return 0;}
        if (weights==null || weights.length==0){return 0;}
        if (capacity<0){return 0;}
        //使用递推方式:dp(i,j):最大承重为j，有前i件物品可选时的最大总价值
        int[][] dp=new int[values.length+1][capacity+1];//数组初始化默认值就是0
        //遍历
        for (int i = 1; i <= values.length; i++) {
            for (int j = 1; j <= capacity; j++) {
                //翻译状态转移方程
                if (j < weights[i-1]) {
                    dp[i][j]=dp[i-1][j];
                } else {
                    dp[i][j]=Math.max(dp[i-1][j], dp[i-1][j-weights[i-1]]+values[i-1]);
                }
            }
        }
        //dp[i][j]==dp[i-1][j-weights[i-1]]+values[i-1] //说明选择了这件物品
        printGoodsInfo(dp, weights, values, capacity);
        System.out.println();
        System.out.println("--------------------------");
        return dp[values.length][capacity];
    }

    //打印出来商品组合信息
    public static void printGoodsInfo(int[][] dp, int[] weights, int[] values, int capacity) {
        //从后往前遍历二维数组
        int i=weights.length;
        int j=capacity;
        //dp[i][j]=
        //循环操作
        while (i > 0 && j > 0) {
            try {
                if (dp[i][j]==dp[i-1][j-weights[i-1]]+values[i-1]) {
                    //说明了weights[i-1]这件物品被选择了
                    System.out.print("选择了"+values[i-1]+"物品；");
                    //j的改变
                    j=j-weights[i-1];
                }
            } catch (ArrayIndexOutOfBoundsException e) {

            }
            //不管是否选择了物品，i都要移动到上一行
            i--;
        }
    }
}  
   循环遍历多辆车并且输出每辆车的物品组合
package com.lg.transport_goods;

import java.text.DecimalFormat;
import java.util.ArrayList;

//参考01背包实现
public class TransportGoods2 {
    //货物体积数据 单位是立方米 转为立方分米
    static Double[] volumeArr = {
            1.18041, 8.92088, 4.58139, 5.29266, 1.23892, 3.93005, 7.53638, 6.92084, 3.89288,
            4.67208, 0.37816, 0.7633, 1.49049, 0.2945, 3.63577, 4.53125, 6.86774, 7.03136,
            8.32038, 3.28645, 0.92165, 6.0227, 6.67724, 2.25087, 6.36347, 0.91234, 0.4131,
            6.03253, 2.10624, 0.94981, 5.49145, 1.84597, 1.64853, 4.24115, 2.70332, 3.73644,
            5.50686, 4.85712, 5.72609, 3.07901, 5.43169, 7.88526, 2.37452, 2.87198, 6.30832,
            3.03864, 3.19001, 3.50305, 0.28338, 9.95386, 3.94953, 6.72467, 3.82848, 3.03825,
            6.27153, 9.97295, 6.87071, 8.19529, 8.23215, 0.75555, 3.89223, 2.5766, 1.29116,
            3.21259, 1.45661, 7.13919, 9.66758, 5.29364, 0.59208, 1.06844, 6.91517, 6.27877,
            1.50904, 6.50522, 1.77932, 6.30585, 1.19917, 4.87037, 1.07854, 7.28688, 3.50365,
            2.16646, 0.5104, 1.01293, 4.91249, 6.23181, 2.64389, 3.06228, 5.61209, 3.58101
    };
    static int capacity = 40 * 1000;
    // 如何判断货物是否装载完毕
    public static void getMaxVolumeMulti(Integer[] volumeArr, Integer capacity) {
        int num=0;
        //判断货物体积数组中是否有数据
        while (volumeArr.length != 0) {
            num++;
            Integer[] arr = getMaxVolume(volumeArr, capacity, num);
            volumeArr=arr;
        }
    }

    //对货物体积进行整数化处理
    public static Integer[] translate(Double[] volumeArr) {
        //准备一个整数数组
        Integer[] arr=new Integer[volumeArr.length];
        //保留小数点后三位的数据
        DecimalFormat decimalFormat = new DecimalFormat("######0.000");
        //对数据进行转换
        for (int i = 0; i < volumeArr.length; i++) {
            String text = decimalFormat.format(volumeArr[i]);
            double v = Double.parseDouble(text);
            arr[i]= (int) (v * 1000);

        }
        return arr;
    }
    /**
     *
     * @param volumeArr
     * @param capcity
     * @return
     */
    public static Integer[] getMaxVolume(Integer[] volumeArr, int capcity, int num) {
        //定义状态数组
        int[][] dp = new int[volumeArr.length + 1][capcity + 1];
        //遍历数据
        for (int i = 1; i <= volumeArr.length; i++) {
            for (int j = 1; j <= capcity; j++) {
                //状态方程
                if (j < volumeArr[i - 1]) {
                    //剩余容积不满足选择该物品
                    dp[i][j] = dp[i - 1][j];
                } else {
                    //选或不选
                    dp[i][j] = Math.max(dp[i - 1][j - volumeArr[i - 1]] + volumeArr[i - 1], dp[i - 1][j]);
                }
            }
        }
        System.out.println();
        System.out.println("------------------------------");
        //打印最大体积值
        System.out.println("第"+num+"辆车，最大组合体积为" + dp[volumeArr.length][capcity]);
        //调用详细货物组合方案信息
        Integer[] newArr = printGoodsInfo(dp, volumeArr, capcity);
        return newArr;
    }

    //打印出来货物组合信息
    public static Integer[] printGoodsInfo(int[][] dp, Integer[] volumeArr, int capacity) {
        //从后往前遍历二维数组
        int i = volumeArr.length;
        int j = capacity;
        //dp[i][j]=
        //循环操作
        while (i > 0 && j > 0) {
            try {
                if (dp[i][j] == dp[i - 1][j - volumeArr[i - 1]] + volumeArr[i - 1]) {
                    //说明了volumeArr[i-1]这件物品被选择了
                    System.out.print("选择了体积为" + volumeArr[i - 1] + "货物；");
                    //j的改变
                    j = j - volumeArr[i - 1];

                    //标记被选择的物品
                    volumeArr[i-1]=0;
                }
            } catch (ArrayIndexOutOfBoundsException e) {

            }
            //不管是否选择了物品，i都要移动到上一行
            i--;
        }
        //物品被选择之后，需要从原始数组中移除,所有数据为0的数据过滤掉
        return getNewArr(volumeArr);
    }

    //剔除选择的物品
    public static Integer[] getNewArr(Integer[] volumeArr) {
        //准备接收的数组
        ArrayList<Integer> list = new ArrayList<>();
        for (int i = 0; i < volumeArr.length; i++) {
            if (volumeArr[i] != 0) {
                list.add(volumeArr[i]);
            }

        }
        //转成数组
        Integer[] arr = new Integer[list.size()];
        return list.toArray(arr);
    }

    public static void main(String[] args) {
        getMaxVolumeMulti(translate(volumeArr), capacity);
    }
}
   
   

   